//  https://leetcode.com/problems/divide-two-integers/description/
// import "fmt"
func divide(dividend int, divisor int) int {
    if dividend == -2147483648 && divisor == -1 {
        return 2147483647
    }  
    if dividend == divisor {
        return 1
    }
    if divisor == -2147483648 {
        return 0
    }
    if divisor == 1 {
        return dividend
    }    
    if divisor == -1 {
        return 0 - dividend
    }    
    if dividend == 0 {
        return 0
    }
    
    var divide_ func(int, int) (int)
    divide_ = func(dividend int, divisor int) (int) {
        // fmt.Println("enter", dividend, divisor)
        if dividend < divisor {
            return 0
        }
        
        factor := 1
        next := divisor
        for dividend > next && next <= 1073741824 {
            if (next << 1) > dividend {
               break
            }
            next = (next << 1)
            factor = (factor << 1)
            // fmt.Println("loop", next, factor)
        }
        
        return factor + divide_(dividend - next, divisor)
    }
    
    add_sign := false
    if dividend < 0 && divisor > 0 {
        add_sign = true
    }
    if dividend > 0 && divisor < 0 {
        add_sign = true
    }
    
    if divisor < 0 {
        divisor = 0 - divisor
    }
    
    var ret int
    if dividend == -2147483648 {
        ret = 1 + divide_(2147483647 - divisor + 1, divisor)
    } else {
        if dividend < 0 {
            dividend = 0 - dividend
        }
        ret = divide_(dividend, divisor)
    }
    
    if add_sign {
        ret = 0 - ret
    }
    return ret
}
